演算法筆記

範例：Peak finding

1. Algorithmic thinking, peak finding

讀書筆記

範圍1, 3, D.1

快速複習矩陣跟矩陣運算方法

D.1 Matrices and matrix operations

$一個m乘n的矩陣A{m,n} = \begin{pmatrix} a{1,1} & a{1,2} & \cdots & a{1,n} \ a{2,1} & a{2,2} & \cdots & a{2,n} \ \vdots & \vdots & \ddots & \vdots \ a{m,1} & a{m,2} & \cdots & a{m,n}

\end{pmatrix}

\begin{pmatrix} 1 & 2 & \cdots \\ 3 & 4 & \cdots \\ \vdots & \vdots & \ddots \end{pmatrix} $

其中$a_{1,1}=1, a_{1,2}=2$，以此類推。

Transpose 矩陣$A^T$則是$\forall a_{i,j} \in A都mapping到A^{T}裡的a_{j,i}$
Vector 則是one-dimentional的矩陣, column vector是$n\times 1$, row vector則是$1\times n$, 可用transpose作轉換。
unit vector $e_i是i_{th}為1，其他都是0的vector$
zero matrix 是元素全為0的矩陣 ## Square matrix 方陣

Diagonal matrix $\forall i \neq j, a_{i,j}=0$
Identity matrix is a diagonal matrix and $\forall a_{i,j}=1$
Tridigonal matrix, $T \text{ is}\forall |i-j|>1, a_{i,j}=0 $
upper-triangle matrix $U \text{ is} \forall i>j, a_{i,j}=0 $
lower-triangle matrix $L \text{ is} \forall i<j, a_{i,j}=0 $
permutation matrix $P$, there is exact one 1 in each column or row, and 0 elsewhere
symmetric matrix $A=A^T$ ## BASIC Matrix operations 基本矩陣運算
add
scalar multiple
compatible is matrix $A,B$ where $A=(a_{i,j})\text{ is }m*n\text{ matrix }$, $B=(b_{i,j})\text{ is }n*p\text{ matrix }$
multiplication $C = AB$ where $C_{i,j}=\displaystyle\sum_{k=1}^{n} a_{i,k}*b_{k,j}$, 計算n方陣需要左列的n次乘法，n－1次加法再乘元素數量＝$n^2$所以各是$n^3, n^2(n-1)$是$\Theta (n^3)$ ## 運算性質
compatiable matrix的乘法 distrubutes or addirion: $A(B+C) = AB+AC$
for n>1, 乘法沒有commutative， ex: $ A = \bigl(\begin{smallmatrix}0&1 \\ 0&0\end{smallmatrix} \bigr), B = \bigl(\begin{smallmatrix}0&0 \\ 1&0\end{smallmatrix} \bigr), AB\neq BA$

Exercises

D.1-1 Show that if A and B are symmetric $n\times n$ matrices, then so are A+B and A-B.

if $A$ and $B$ are symmetric, then $a_{i,j} = a_{j,i} ,for \forall i,j,0<=i<n, 0<=j<n$ $C = A+B, c_{i,j} = a_{i,j}+b_{i,j}\text{, since A,B are symmetric,} a_{i,j} = a_{j,i} ,for \forall i,j,0<=i<n, 0<=j<n $

thus, $c_{i,j} = a_{j,i}+b_{j,i}= c_{j,i}, C$ is symmetric

D.1-2 Prove that $(AB)^T= B^TA^T$ and that $A^TA$ is always a symmetric matrix.
D.1-3 Prove that the product of two lower-triangular matrices is lower-triangular.
D.1-4 Prove that $P$ is a $n\times n$permutation matrix and $A$ is a $n\times n$matrix,then the matrix product $PA$ is $A$ with its rows permuted, and the matrix product $AP$ is $A$ with its columns permuted. Prove that the product of two permutation matrices is a permutation matrix.